package com.zhj.bz.datastructure.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zhj
 */
public class PolandNotation {
    public static void main(String[] args) {
        String expression = "（30+40）*50-600";
        String suffixExpression = "30 40 + 50 * 600 -";
        List<String> list = getListString(suffixExpression);
        System.out.println(list);
        list = parseSuffixExpressionList(expression);
        System.out.println(list);
        System.out.println(calculate(list));
    }

    private static List<String> getExpressionListString(String expression) {
        List<String> list = new ArrayList<>();
        int index = 0;
        StringBuffer sb = new StringBuffer();
        char c;
        do {
            if ((c=expression.charAt(index))< 48 || (c=expression.charAt(index)) > 57) {
                list.add("" + c);
                index++;
            } else {
                sb.setLength(0);
                while (index < expression.length() && (c=expression.charAt(index))>= 48 && (c=expression.charAt(index)) <= 57) {
                    sb.append(c);
                    index++;
                }
                list.add(sb.toString());
            }
        } while (index < expression.length());
        return list;
    }

    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String s : split) {
            list.add(s);
        }
        return list;
    }
    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                int result = 0;
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                switch (s) {
                    case "+":
                        result = num1 + num2;
                        break;
                    case "-":
                        result = num1 - num2;
                        break;
                    case "*":
                        result = num1 * num2;
                        break;
                    case "/":
                        result = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException("运算符不符合规定！！！");
                }
                stack.push(result + "");
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * 中缀表达式转逆波兰表达式
     * @param expression
     * @return
     */
    public static List<String> parseSuffixExpressionList(String expression) {
        List<String> expressionList = getExpressionListString(expression);
        System.out.println(expressionList);
        Stack<String> stack = new Stack<>();
        List<String> list = new ArrayList();
        for (String s : expressionList) {
            if (s.matches("\\d+")) {
                list.add(s);
            } else if (s.equals("（")) {
                stack.push(s);
            } else if (s.equals("）")) {
                // 消除括号 将括号内元素放入list
                while (!stack.peek().equals("（")) {
                    list.add(stack.pop());
                }
                // 将小括号弹出
                stack.pop();
            } else {
                // 判断优先级
                while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(s)) {
                    list.add(stack.pop());
                }
                stack.push(s);
            }
        }
        while (stack.size() != 0) {
            list.add(stack.pop());
        }

        return list;
    }
}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int result = 0;
        if (operation.equals("（") || operation.equals("）")) {
            return result;
        }
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "/":
                result = MUL;
                break;
            case "*":
                result = DIV;
                break;
            default:
                throw new RuntimeException("不存在的运算符");
        }
        return result;
    }
}
